package lcci;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class leetcode1705 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findLongestSubarray(new String[]{"A", "1", "B", "C", "D", "2", "3", "4", "E", "5", "F", "G", "6", "7", "H", "I", "J", "K", "L", "M"})));
        System.out.println(Arrays.toString(findLongestSubarray(new String[]{"42", "10", "O", "t", "y", "p", "g", "B", "96", "H", "5", "v", "P", "52", "25", "96", "b", "L", "Y", "z", "d", "52", "3", "v", "71", "J", "A", "0", "v", "51", "E", "k", "H", "96", "21", "W", "59", "I", "V", "s", "59", "w", "X", "33", "29", "H", "32", "51", "f", "i", "58", "56", "66", "90", "F", "10", "93", "53", "85", "28", "78", "d", "67", "81", "T", "K", "S", "l", "L", "Z", "j", "5", "R", "b", "44", "R", "h", "B", "30", "63", "z", "75", "60", "m", "61", "a", "5", "S", "Z", "D", "2", "A", "W", "k", "84", "44", "96", "96", "y", "M"})));
    }

    //    number1-number2=capital1-capital2;
//    number1-capital1=number2-capital2;
    public static String[] findLongestSubarray(String[] array) {
        int[] numberPrefixCount = new int[array.length + 1];
        int[] capitalPrefixCount = new int[array.length + 1];

        for (int i = 0; i < array.length; i++) {
            if (Character.isDigit(array[i].charAt(0))) {
                numberPrefixCount[i + 1] = numberPrefixCount[i] + 1;
                capitalPrefixCount[i + 1] = capitalPrefixCount[i];
            } else {
                numberPrefixCount[i + 1] = numberPrefixCount[i];
                capitalPrefixCount[i + 1] = capitalPrefixCount[i] + 1;
            }
        }

        int start = 0;
        int end = 0;

        Map<Integer, Integer> count = new HashMap<>();
        for (int i = 0; i < numberPrefixCount.length; i++) {
            int diff = numberPrefixCount[i] - capitalPrefixCount[i];
            if (diff == 0) {
                //从某点到头到情况
                if (i > end - start) {
                    start = 0;
                    end = i;
                }
            } else {
                Integer index = count.get(diff);
                if (index != null) {
                    //从某点到diff点，diff点更小不用更新map
                    if (i - index > end - start) {
                        start = index;
                        end = i;
                    }
                } else {
                    count.put(diff, i);
                }
            }

        }

        return Arrays.copyOfRange(array, start, end);
    }
}
